package timingAttack;

/***
 * 
 * 
 * @author akabdul
 */


import java.math.BigInteger;
import java.math.MathContext;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Arrays;


public class HashCollision {
	
	static int tsize = 100000;
	static long[][] tdiff = new long[256][tsize];
	static double[] mean = new double[256];
	static long unitnanos = 25;
	
	public static void main(String[] args) {
		try {
			MessageDigest md = MessageDigest.getInstance("MD5");
			String message = "Test";
			
			md.update(message.getBytes(),0,message.length());
			byte[] digest = md.digest();
			
			//checkTimingAccruracy(digest);
		    
		
			byte[] recovered =breakDigest2(digest);
			System.out.println("recovered digest\t= " + toHex(recovered));
			System.out.println("original digest\t= " + toHex(digest));
			System.out.println("IsEqual = " + equals(recovered, digest));
			
		}
		catch (NoSuchAlgorithmException e) { e.printStackTrace(); }
		
	}
	
	public static String toHex(byte[] digest) {
		String hexString = "";
		
		for (int i = 0; i < digest.length-1; i++) {
				hexString += toHex(digest[i]) + ":";
		}	
		hexString += toHex(digest[digest.length-1]);
		
		return hexString;
		
				
	}
	
	public static String toHex(byte digest) {
		
		if(digest>=0 && digest<=15)
			return String.format("0%x",digest);
		else
			return String.format("%x",digest);
		
	}
	
	/* the purpose is to introduce noticeable overhead to loop */
	public static int incr(int i ) {
		try {
			Thread.sleep(5);
		} 
		catch (InterruptedException e) { e.printStackTrace(); }
		
		return ++i;
	}
	
	public static boolean equals(byte[] digest1, byte[] digest2) {
		for (int i = 0; i < digest2.length; ++i /*i= incr(i)*/) {
			if(digest1[i] != digest2[i])
				return false;
		}
		return true;
	}
	
	static double getInitialMinMean(byte[] master, byte[] digest) {
		byte b = 0x00;
		for(int j = 0; j < 256; j++) {// check bytes 0x00..0xff
			master[0] = b++;
			//System.out.println(toHex(master));
			
			for(int k=0; k< tsize-1; k++) { // record timings for this byte
				long start = System.nanoTime();
				equals(master, digest);
				long end = System.nanoTime();
				
				tdiff[j][k] = end - start;	
				
				if(k % 1000 == 0) {
//					try {
//						Thread.sleep(5);
//					} catch (InterruptedException e) {
//						
//						e.printStackTrace();
//					}
				}
				
				//System.out.print(tdiff[j][k] + " ");
			}
			//System.out.println();
		}
		
		// calculate mean for this array position
		b = 0x00;
		for (int j = 0; j < 256; j++) {
			mean[j] = Statistics.trimmedMean(tdiff[j]);
			System.out.println("Byte = " + toHex(b++) + ", mean = " + mean[j]);
		}
		// pick up the byte with the smallest mean ??
		int minMean = Statistics.IndexOfMin(mean);
		
		// set to byte with maximum mean 
		int maxMean = Statistics.IndexOfMax(mean);
		master[0] = (byte) maxMean;
		
		return mean[minMean];
	}
	
	public static byte[] breakDigest2(byte[] digest) {
		
		int dlength = digest.length;
		byte[] master = new byte[dlength];
		
		// check the initial minimum mean
		//double observedMinMean = getInitialMinMean(master, digest);
		
		//System.out.println("initial observed mean = " + observedMinMean);
		//System.out.println("correct byte = " + toHex(master[0]));
		
		for (int i = 0; i < dlength; i++) { // repeat array positions 1..255
			byte b = 0x00;
			//System.out.println("calc varianace for byte position " + i );
			
			for(int j = 0; j < 256; j++) {// check bytes 0x00..0xff
				master[i] = b++;
				//System.out.println(toHex(master));
				
				for(int k=0; k< tsize-1; k++) { // record timings for this byte
					long start = System.nanoTime();
					equals(master, digest);
					long end = System.nanoTime();
					
					tdiff[j][k] = end - start;	
					
					//System.out.print(tdiff[j][k] + " ");
				}
				//System.out.println();
			}
			
			// calculate mean for this array position
			b = 0x00;
			for (int j = 0; j < 256; j++) {
				mean[j] = Statistics.trimmedMean(tdiff[j]);
				//System.out.println("Byte = " + toHex(b++) + ", mean = " + mean[j]);
			}
			
			// pick up byte with the maximum mean value
			int maxMean = Statistics.IndexOfMax(mean);
			
			// pick up the byte with the smallest mean ??
			int minMean = Statistics.IndexOfMin(mean);
			
			// variance of means
			double variance = Statistics.variance(mean);
			
			// mean of means
			double meanOfMeans = Statistics.mean(mean);
			
			// diff between maxMean and mean of means
			double diffMeans = mean[maxMean] - meanOfMeans;
			
			// diff between maxMean and minMean
			double diffMaxMinMean = mean[maxMean] - mean[minMean];
			
			// median of means 
			double median = Statistics.mean(mean);
			
			// store the correct byte in master
			master[i] = (byte) maxMean;
			System.out.println("position = " + i + ", correct byte = " + toHex(master[i])
								+ ", max mean = " + mean[maxMean]
								+ ", min mean = " + mean[minMean]
								+ ", diffMaxMinMeans = " + diffMaxMinMean
								+ ", mean of means = " + meanOfMeans
								+ ", variance = " + variance
								+ ", diffMeans = " + diffMeans
								+ ", median = " + median);
			
			// check progress ..? and adjust 
//			if(approxEqual(mean[minMean], observedMinMean)) {
//				System.out.println("\n:: Approx equal min means. Repeating last cycle ::\n");
//				i--;
//			}
//			else {
//				System.out.println("\n:: Progress to next byte position ::\n");
//				observedMinMean = mean[minMean];
//			}
			
			//System.exit(0);
		}
		
		
		
		// check the 
		
		return master;
	}
	
	static boolean approxEqual(double v1, double v2) {
		long diff = Math.round(v1) - Math.round(v2);
		
		return diff < unitnanos; 
	}
	
	public static void checkTimingAccruracy(byte[] digest) {
		byte[] testDigest = {0x00,0x00, 0x00, 0x00,
							0x00,0x00, 0x00, 0x00,
							0x00,0x00, 0x00, 0x00,
							0x00,0x00, 0x00, 0x00};
		
		
		// another testDigest with half the bytes equal to the given digest
		byte[] testDigest2 = new byte[digest.length];
		for (int i = 0; i < testDigest2.length/2; i++) {
			testDigest2[i] = digest[i];
		}
		
		byte b = 0x00;
		for (int i = 0; i < 256; i++) {
			testDigest[0] = b++;
			long start = System.nanoTime();
			equals(testDigest, digest);
			long end = System.nanoTime();
			
			System.out.println("Testdigest = " + toHex(testDigest) + ", timediff = " + (end-start));
		
			testDigest2[8] = b;
			start = System.nanoTime();
			equals(testDigest2, digest);
			end = System.nanoTime();
			
			System.out.println("Testdigest2 = " + toHex(testDigest2) + ", timediff = " + (end-start));
		
		
		}
	}
	
	public static byte[] breakDigest(byte[] digest) {
		/* init a digest with 0 bytes */
		byte[] bruteForce = {0x00,0x00, 0x00, 0x00,
							0x00,0x00, 0x00, 0x00,
							0x00,0x00, 0x00, 0x00,
							0x00,0x00, 0x00, 0x00};
		
		/* try every possible 8-bit byte 0x00 to 0xff for each array position
		   and time the equality operation 										*/
		
		for (int i = 0; 
				
				i < bruteForce.length; 
				
				i++) {
			long maxTime =0;
			byte b =0x00; 
			byte correctByte = 0x00;
			
			long start = 0, end = 0;
			
			for(int i1 = 0; i1 < 256; i1++) {// inner loop to count from 0 to 255 
				
				start = System.nanoTime();
				equals(digest, bruteForce);
				end = System.nanoTime();
				
				long timeDiff = end-start;
				
				System.out.println( "iteration " + i 
								 + String.format(", start = %d, end = %d, " +
						         "Time diff = %d, byte = %x",start,end,timeDiff,b));
				
				/* pick the byte alternative with max time*/
				if(maxTime < timeDiff) {
					correctByte = b;
					maxTime = timeDiff;
					
					System.out.println("iteration = " + i
										+"CORRECT BYTE = " 
										+ String.format("%x", b));
					//break;
				}
				
				/* try next byte for this position */
				bruteForce[i] = ++b;
			}
			
			/* set correct byte to the current position in array */
			bruteForce[i] = correctByte;
		}
		
		return bruteForce;
	}

}
